package demo.practice.leetcode_offer;

public class Offer42_2 {

    public int maxSubArray(int[] nums) {

        int[] store = new int[nums.length + 1];

        int max = Integer.MIN_VALUE;
        for (int i = 1; i < store.length; i++) {
            store[i] = nums[i - 1] + store[i - 1];
            max = Math.max(store[i], max);
        }

        int min = Integer.MAX_VALUE;
        for (int i = 2; i < store.length; i++) {

            min = Math.min(store[i - 1], min);//选出之前最小的
            max = Math.max(max, store[i]-min);
        }

        return max;
    }
}
